When confidential information (for example, a secret key for use in encryption) is stored, there are the threat of loss or breakage of data and the threat of theft of data. For the former threat, the creation of a copy of confidential information would be effective, but the creation of the copy would result in an increase in the threat of theft. As one information security technology for solving such a problem, there is a secret sharing scheme.
In a (k,n) threshold scheme, which is one secret sharing scheme, distribution-codes confidential information which is object of protection into n pieces of information, and the (k,n) threshold scheme has a feature that the confidential information can be restored if k or more arbitrary pieces of distributed information are collected, and the information relating the confidence cannot be obtained if (k−1) or less arbitrary pieces of distributed information are collected. Accordingly, even if up to (k−1) pieces of distributed information are stolen, confidential information cannot be read, and even if up to (n−k) pieces of distributed information are broken, confidential information can be restored. This (k,n) threshold scheme is described in detail, for example, in Non-Patent Document 1 (Adi Shamir, “How to share a secret,” Comm. ACM, 22(11), pp. 612-613 (1979)).
In the following, consider problems when confidential information is restored in a situation where distributed information is legitimately created and distributed in accordance with a normal (k,n) threshold scheme.
When confidential information is to be restored, distributed information must be collected from other sources which hold the distributed information. In this event, parties to whom a request has been made for distributed information do not always supply the values, which they have obtained, to a restoring party without tampering with them. In this regard, “tampering” herein referred to includes not only intentional changes but also unintentional changes such as a failed device, simple mistake and the like.
If confidential information is restored using tampered distributed information, the resulting value can be a value different from the confidential information. For this reason, an approach is desired to permit a secret sharing scheme to detect with a high probability that a tampered value exists within distributed information for use in restoration. Also, distributed information is obtained by a variety of means, depending on how the information is used, so that it is desirable that a tampered value be detected with a high degree of probability when distributed information is obtained on the basis of any probability distribution.
As one technology for solving these problems, a method described in Non-Patent Document 2 (Martin Tompa, Heather Woll, “How to Share a Secret with Cheaters,” Journal of Cryptology, vol. 1, pages 133-138, 1988.) is known.
Non-Patent Document 2 describes a (k,n) threshold scheme which can detect falsity with a probability of (1−ε) when distributed information is obtained on the basis of any probability distribution. In the method described in Non-Patent Document 2, when confidential information is a set of a number s of elements, distribution information is a set of a number ((s−1)(k−1)/ε+k)^2 of elements.
Also, Non-Patent Document 3 (Wakaha Ogata, Kaoru Kurosawa, Douglas R Stinson, “Optimum Secret Sharing Scheme Secure Against Cheating,” SIAM Journal on Discrete Mathematics, vol. 20, no 1, pages 79-95, 2006.) describes a (k,n) threshold scheme which is capable of sensing falsity with a probability of (1−ε) on condition that distributed information is selected in accordance with a uniform probability distribution. In the method described in Non-Patent Document 3, when confidential information is a set of a number s of elements, distribution information is a set of a number (1+(s−1)/ε) of elements.
However, the conventional secret sharing schemes as described above has a problem in which the amount of distributed information becomes large as compared with the amount of confidential information.